空间数据结构和算法 (scipy.spatial )

您所在的位置：网站首页 › python 计算几何 scipy › 空间数据结构和算法 (scipy.spatial )

空间数据结构和算法 (scipy.spatial )

#空间数据结构和算法 (scipy.spatial ) | 来源: 网络整理| 查看: 265

Voronoi图¶

Voronoi图是将空间细分为一组给定点的最近邻域。

使用以下两种方法可以接近此对象 scipy.spatial 。首先，可以使用 KDTree 要回答“哪个点最接近这个点”的问题，并这样定义区域：

>>> from scipy.spatial import KDTree >>> points = np.array([[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], ... [2, 0], [2, 1], [2, 2]]) >>> tree = KDTree(points) >>> tree.query([0.1, 0.1]) (0.14142135623730953, 0)

所以重点是 (0.1, 0.1) 属于区域 0 。在颜色方面：

>>> x = np.linspace(-0.5, 2.5, 31) >>> y = np.linspace(-0.5, 2.5, 33) >>> xx, yy = np.meshgrid(x, y) >>> xy = np.c_[xx.ravel(), yy.ravel()] >>> import matplotlib.pyplot as plt >>> dx_half, dy_half = np.diff(x[:2])[0] / 2., np.diff(y[:2])[0] / 2. >>> x_edges = np.concatenate((x - dx_half, [x[-1] + dx_half])) >>> y_edges = np.concatenate((y - dy_half, [y[-1] + dy_half])) >>> plt.pcolormesh(x_edges, y_edges, tree.query(xy)[1].reshape(33, 31), shading='flat') >>> plt.plot(points[:,0], points[:,1], 'ko') >>> plt.show()

然而，这并没有给出作为几何对象的Voronoi图。

线和点的表示可以通过中的qhull包装器再次获得 scipy.spatial ：

>>> from scipy.spatial import Voronoi >>> vor = Voronoi(points) >>> vor.vertices array([[0.5, 0.5], [0.5, 1.5], [1.5, 0.5], [1.5, 1.5]])

Voronoi顶点表示形成Voronoi区域的多边形边的点集。在本例中，有9个不同的区域：

>>> vor.regions [[], [-1, 0], [-1, 1], [1, -1, 0], [3, -1, 2], [-1, 3], [-1, 2], [0, 1, 3, 2], [2, -1, 0], [3, -1, 1]]

负值 -1 再次表示无穷远处的一个点。事实上，只有一个地区， [0, 1, 3, 2] ，是有界的。请注意，由于与上面的Delaunay三角剖分中类似的数值精度问题，Voronoi区域可能比输入点少。

将分隔区域的脊(二维中的线)描述为与凸面壳片类似的简化集合：

>>> vor.ridge_vertices [[-1, 0], [-1, 0], [-1, 1], [-1, 1], [0, 1], [-1, 3], [-1, 2], [2, 3], [-1, 3], [-1, 2], [1, 3], [0, 2]]

这些数字表示组成线段的Voronoi顶点的索引。 -1 又是一个无穷远的点-12条直线中只有4条是有界线段，而其他的延伸到无穷远。

Voronoi山脊垂直于输入点之间绘制的线。还记录了每个脊对应的两个点：

>>> vor.ridge_points array([[0, 3], [0, 1], [2, 5], [2, 1], [1, 4], [7, 8], [7, 6], [7, 4], [8, 5], [6, 3], [4, 5], [4, 3]], dtype=int32)

这些信息加在一起，足以构成完整的图表。

我们可以把它画成如下图。首先，点和Voronoi顶点：

>>> plt.plot(points[:, 0], points[:, 1], 'o') >>> plt.plot(vor.vertices[:, 0], vor.vertices[:, 1], '*') >>> plt.xlim(-1, 3); plt.ylim(-1, 3)

绘制有限线段与绘制凸壳一样，但现在我们必须注意无限边：

>>> for simplex in vor.ridge_vertices: ... simplex = np.asarray(simplex) ... if np.all(simplex >= 0): ... plt.plot(vor.vertices[simplex, 0], vor.vertices[simplex, 1], 'k-')

延伸到无穷远的山脊需要稍微小心一点：

>>> center = points.mean(axis=0) >>> for pointidx, simplex in zip(vor.ridge_points, vor.ridge_vertices): ... simplex = np.asarray(simplex) ... if np.any(simplex = 0][0] # finite end Voronoi vertex ... t = points[pointidx[1]] - points[pointidx[0]] # tangent ... t = t / np.linalg.norm(t) ... n = np.array([-t[1], t[0]]) # normal ... midpoint = points[pointidx].mean(axis=0) ... far_point = vor.vertices[i] + np.sign(np.dot(midpoint - center, n)) * n * 100 ... plt.plot([vor.vertices[i,0], far_point[0]], ... [vor.vertices[i,1], far_point[1]], 'k--') >>> plt.show()

也可以使用以下命令创建此图 scipy.spatial.voronoi_plot_2d 。

沃罗诺伊图可以用来创作有趣的创作艺术。尝试使用此设置 mandala 函数来创建您自己的！

>>> import numpy as np >>> from scipy import spatial >>> import matplotlib.pyplot as plt >>> def mandala(n_iter, n_points, radius): ... """Creates a mandala figure using Voronoi tesselations. ... ... Parameters ... ---------- ... n_iter : int ... Number of iterations, i.e. how many times the equidistant points will ... be generated. ... n_points : int ... Number of points to draw per iteration. ... radius : scalar ... The radial expansion factor. ... ... Returns ... ------- ... fig : matplotlib.Figure instance ... ... Notes ... ----- ... This code is adapted from the work of Audrey Roy Greenfeld [1]_ and Carlos ... Focil-Espinosa [2]_, who created beautiful mandalas with Python code. That ... code in turn was based on Antonio Sánchez Chinchón's R code [3]_. ... ... References ... ---------- ... .. [1] https://www.codemakesmehappy.com/2019/09/voronoi-mandalas.html ... ... .. [2] https://github.com/CarlosFocil/mandalapy ... ... .. [3] https://github.com/aschinchon/mandalas ... ... """ ... fig = plt.figure(figsize=(10, 10)) ... ax = fig.add_subplot(111) ... ax.set_axis_off() ... ax.set_aspect('equal', adjustable='box') ... ... angles = np.linspace(0, 2*np.pi * (1 - 1/n_points), num=n_points) + np.pi/2 ... # Starting from a single center point, add points iteratively ... xy = np.array([[0, 0]]) ... for k in range(n_iter): ... t1 = np.array([]) ... t2 = np.array([]) ... # Add `n_points` new points around each existing point in this iteration ... for i in range(xy.shape[0]): ... t1 = np.append(t1, xy[i, 0] + radius**k * np.cos(angles)) ... t2 = np.append(t2, xy[i, 1] + radius**k * np.sin(angles)) ... ... xy = np.column_stack((t1, t2)) ... ... # Create the Mandala figure via a Voronoi plot ... spatial.voronoi_plot_2d(spatial.Voronoi(xy), ax=ax) ... ... return fig >>> # Modify the following parameters in order to get different figures >>> n_iter = 3 >>> n_points = 6 >>> radius = 4 >>> fig = mandala(n_iter, n_points, radius) >>> plt.show()

【本文地址】

空间数据结构和算法 (scipy.spatial )

空间数据结构和算法 (scipy.spatial )

今日新闻

推荐新闻